package tool.tree.binary;

import java.util.*;

/**
 * 自己写的二叉树工具类
 */
public class BinaryTree {

    /**
     * 转为二叉树
     *
     * @param nums Integer列表
     * @return 二叉树根节点
     */
    public static TreeNode getTreeByList(Integer[] nums) {
        TreeNode cNode, root = new TreeNode(nums[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int i = 1;
        while (i < nums.length) {
            cNode = queue.remove();
            if (nums[i] != null) queue.add(cNode.left = new TreeNode(nums[i]));
            i++;
            if (i < nums.length)
                if (nums[i] != null) queue.add(cNode.right = new TreeNode(nums[i]));
            i++;
        }
        return root;
    }

    /**
     * dfs遍历输出
     *
     * @param root 二叉树根节点
     */
    public static void dfs(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        TreeNode node = root;
        while (!stack.empty()) {
            System.out.println(node.val);
            node = stack.pop();
            //根据栈的特性所以右结点先入栈
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
    }

    /**
     * 二叉树的层序遍历
     *
     * @param root 根节点
     * @return 数组，元素是每一层的元素
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        // 存储结果的数组
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int size = queue.size(); // 记录当前有几个元素，这一层就有几个元素
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll(); // 遍历的元素
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            res.add(new ArrayList<>(level));
        }
        return res;
    }

    /**
     * 返回数的高度，递归方式
     *
     * @param root 根节点
     * @return 高度
     */
    public static int height(TreeNode root) {
        if (root == null) return 0;
        else return Math.max(height(root.left), height(root.right)) + 1;
    }

    /**
     * 可视化打印
     *
     * @param root 二叉树根节点
     */
    public static void print(TreeNode root) {
        List<List<Integer>> lines = new ArrayList<List<Integer>>();

        List<TreeNode> level = new ArrayList<TreeNode>();
        List<TreeNode> next = new ArrayList<TreeNode>();

        level.add(root);
        int nn = 1;

        int widest = 0;

        while (nn != 0) {
            List<Integer> line = new ArrayList<Integer>();

            nn = 0;

            for (TreeNode n : level) {
                if (n == null) {
                    line.add(null);

                    next.add(null);
                    next.add(null);
                } else {
                    Integer aa = n.val;
                    line.add(aa);
                    if (aa.toString().length() > widest) widest = aa.toString().length();

                    next.add(n.left);
                    next.add(n.right);

                    if (n.left != null) nn++;
                    if (n.right != null) nn++;
                }
            }

            if (widest % 2 == 1) widest++;

            lines.add(line);

            List<TreeNode> tmp = level;
            level = next;
            next = tmp;
            next.clear();
        }

        int perpiece = lines.get(lines.size() - 1).size() * (widest + 4);
        for (int i = 0; i < lines.size(); i++) {
            List<Integer> line = lines.get(i);
            int hpw = (int) Math.floor(perpiece / 2f) - 1;

            // print line of numbers
            for (int j = 0; j < line.size(); j++) {

                Integer fnum = line.get(j);

                String f;
                if (fnum == null) f = "n ";
                else f = fnum.toString();


                int gap1 = (int) Math.ceil(perpiece / 2f - f.length() / 2f);
                int gap2 = (int) Math.floor(perpiece / 2f - f.length() / 2f);

                // a number
                for (int k = 0; k < gap1; k++) {
                    System.out.print(" ");
                }
                System.out.print(f);
                for (int k = 0; k < gap2; k++) {
                    System.out.print(" ");
                }
            }
            System.out.println();

            perpiece /= 2;
        }
    }


}


